package main.剑指OfferⅡ;

import java.util.*;

public class Day37_Day40 {
    public static void main(String[] args) {
        System.out.println("**************************Day37**************************");
        System.out.println("剑指OfferⅡ108.单词演变");
        System.out.println("剑指OfferⅡ109.开密码锁");
        System.out.println("剑指OfferⅡ110.所有路径");
        System.out.println("**************************Day38**************************");
        System.out.println("剑指OfferⅡ111.计算除法");
        System.out.println("剑指OfferⅡ112.最长递增路径");
        System.out.println("剑指OfferⅡ113.课程顺序");
        System.out.println("**************************Day39**************************");
        System.out.println("剑指OfferⅡ114.外星文字典");
        System.out.println("剑指OfferⅡ115.重建序列");
        System.out.println("剑指OfferⅡ116.省份数量");
        System.out.println("**************************Day40**************************");
        System.out.println("剑指OfferⅡ117.相似的字符串");
        System.out.println("剑指OfferⅡ118.多余的边");
        System.out.println("剑指OfferⅡ119.最长连续序列");
    }
}

class Offer108{
    Map<String, Integer> wordId = new HashMap<String, Integer>();
    List<List<Integer>> edge = new ArrayList<List<Integer>>();
    int nodeNum = 0;

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        for (String word : wordList) {
            process1(word);
        }
        process1(beginWord);
        if (!wordId.containsKey(endWord)) {
            return 0;
        }
        int[] dis = new int[nodeNum];
        Arrays.fill(dis, Integer.MAX_VALUE);
        int beginId = wordId.get(beginWord), endId = wordId.get(endWord);
        dis[beginId] = 0;

        Queue<Integer> que = new LinkedList<Integer>();
        que.offer(beginId);
        while (!que.isEmpty()) {
            int x = que.poll();
            if (x == endId) {
                return dis[endId] / 2 + 1;
            }
            for (int it : edge.get(x)) {
                if (dis[it] == Integer.MAX_VALUE) {
                    dis[it] = dis[x] + 1;
                    que.offer(it);
                }
            }
        }
        return 0;
    }

    public void process1(String word) {
        process2(word);
        int id1 = wordId.get(word);
        char[] array = word.toCharArray();
        int length = array.length;
        for (int i = 0; i < length; ++i) {
            char tmp = array[i];
            array[i] = '*';
            String newWord = new String(array);
            process2(newWord);
            int id2 = wordId.get(newWord);
            edge.get(id1).add(id2);
            edge.get(id2).add(id1);
            array[i] = tmp;
        }
    }

    public void process2(String word) {
        if (!wordId.containsKey(word)) {
            wordId.put(word, nodeNum++);
            edge.add(new ArrayList<Integer>());
        }
    }
//    char[][] wordArr;
//    char[] targetArr;
//    int min=Integer.MAX_VALUE;
//    public int process2(char[] str1,char[] str2){//计算差值
//        int count=0;
//        for (int i=0;i<str1.length;i++){
//            if (str2[i]!=str1[i]) count++;
//        }
//        return count;
//    }
//    public void process1(char[] lastArr,boolean[] flag,int times){
//        if (process2(lastArr,targetArr)==0) {//转换成功
//            min=Math.min(min,times);
//            return;
//        }
//        for (int i=0;i< wordArr.length;i++){
//            if (!flag[i]&&process2(lastArr,wordArr[i])==1){//满足此次转换，未被使用且仅差一个字符
//                flag[i]=true;//使用
//                process1(wordArr[i],flag.clone(),times+1);//进入下层
//                flag[i]=false;//撤销使用
//            }
//        }
//    }
//    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
//        boolean[] flag=new boolean[wordList.size()];
//        wordArr=new char[wordList.size()][];
//        for (int i=0;i< wordArr.length;i++){
//            wordArr[i]=wordList.get(i).toCharArray();
//        }
//        targetArr=endWord.toCharArray();
//        process1(beginWord.toCharArray(),flag,0);
//        return min==Integer.MAX_VALUE ? 0 : min+1;
//    }
}

class Offer109{
    public int openLock(String[] deadends, String target) {
        if ("0000".equals(target)) return 0;
        Set<String> dead = new HashSet<String>();
        for (String deadend : deadends) dead.add(deadend);
        if (dead.contains("0000")) return -1;
        int step = 0;
        Queue<String> queue = new LinkedList<String>();
        queue.offer("0000");
        Set<String> seen = new HashSet<String>();
        seen.add("0000");
        while (!queue.isEmpty()) {
            ++step;
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                String status = queue.poll();
                for (String nextStatus : get(status)) {
                    if (!seen.contains(nextStatus) && !dead.contains(nextStatus)) {
                        if (nextStatus.equals(target)) return step;
                        queue.offer(nextStatus);
                        seen.add(nextStatus);
                    }
                }
            }
        }
        return -1;
    }

    public char numPrev(char x) {
        return x == '0' ? '9' : (char) (x - 1);
    }

    public char numSucc(char x) {
        return x == '9' ? '0' : (char) (x + 1);
    }

    // 枚举 status 通过一次旋转得到的数字
    public List<String> get(String status) {
        List<String> ret = new ArrayList<String>();
        char[] array = status.toCharArray();
        for (int i = 0; i < 4; ++i) {
            char num = array[i];
            array[i] = numPrev(num);
            ret.add(new String(array));
            array[i] = numSucc(num);
            ret.add(new String(array));
            array[i] = num;
        }
        return ret;
    }
}

class Offer110{
    List<List<Integer>> list;
    int[][] graph;
    public void process(List<Integer> lastList,int point){
        List<Integer> curList=new ArrayList<>(lastList);
        int[] curArr=graph[point];
        curList.add(point);
        if (point==graph.length-1){//成功到达
            list.add(curList);
            return;
        }
        if (curArr.length==0) return;//无路
        for (int num:curArr){
            process(curList,num);
        }
    }
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        this.graph=graph;
        list=new ArrayList<>();
        List<Integer> curList=new ArrayList<>();
        process(curList,0);
        return list;
    }
}

class Offer111{
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int cnt=0;
        HashMap<String,Integer> map=new HashMap<>();
        int n=equations.size();
        for(int i=0;i<n;i++){//哈希预处理
            for(int j=0;j<2;j++){
                if(!map.containsKey(equations.get(i).get(0)))
                    map.put(equations.get(i).get(0),cnt++);
                if(!map.containsKey(equations.get(i).get(1)))
                    map.put(equations.get(i).get(1),cnt++);
            }
        }
        double [][] graph=new double [cnt][cnt];
        for(int i=0;i<cnt;i++){//建图预处理
            Arrays.fill(graph[i],-1.0);
        }
        for(int i=0;i<n;i++){//建图,乘积
            int va=map.get(equations.get(i).get(0));
            int vb=map.get(equations.get(i).get(1));
            graph[va][vb]=values[i];
            graph[vb][va]=1.0/values[i];
        }
        for(int k=0;k<cnt;k++){//Floyd算法
            for(int i=0;i<cnt;i++){
                for(int j=0;j<cnt;j++){
                    if(graph[i][k]>0&&graph[k][j]>0)
                        graph[i][j]=graph[i][k]*graph[k][j];
                }
            }
        }
        int m=queries.size();
        double [] res=new double [m];
        for(int i=0;i<m;i++){//获取结果
            List<String> query=queries.get(i);
            double tmp=-1.0;
            if(map.containsKey(query.get(0))&&map.containsKey(query.get(1))){
                int va=map.get(query.get(0));
                int vb=map.get(query.get(1));
                if(graph[va][vb]>0) tmp=graph[va][vb];
            }
            res[i]=tmp;
        }
        return res;
    }
}

class Offer112{
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int rows, columns;

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        rows = matrix.length;
        columns = matrix[0].length;
        int[][] memory = new int[rows][columns];
        int ans = 0;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < columns; ++j) {
                ans = Math.max(ans, process(matrix, i, j, memory));
            }
        }
        return ans;
    }

    public int process(int[][] matrix, int row, int column, int[][] memory) {
        if (memory[row][column] != 0) {
            return memory[row][column];
        }
        ++memory[row][column];
        for (int[] dir : dirs) {
            int newRow = row + dir[0], newColumn = column + dir[1];
            if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] > matrix[row][column]) {
                memory[row][column] = Math.max(memory[row][column], process(matrix, newRow, newColumn, memory) + 1);
            }
        }
        return memory[row][column];
    }
}

class Offer113{
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Deque<Integer> queue=new LinkedList<>();
        int [] ins=new int [numCourses];//入度数
        int [] res=new int [numCourses];
        int cnt=0;//一个指针，表示res数组实际有的元素个数
        int n=prerequisites.length;
        for(int i=0;i<n;i++){
            ins[prerequisites[i][0]]++;
        }
        for(int i=0;i<numCourses;i++){//先找到没有入度的结点，入队
            if(ins[i]==0) queue.offer(i);
        }
        while(!queue.isEmpty()){
            int peek=queue.poll();//将队列中的队首元素出队
            res[cnt++]=peek;
            for(int []p:prerequisites){
                if(p[1]==peek){
                    ins[p[0]]--;
                    if(ins[p[0]]==0){
                        queue.offer(p[0]);
                    }
                }
            }
        }
        return cnt==numCourses ? res : new int [0];
//        int[][] arr=new int[numCourses][numCourses];//邻接矩阵
//        int[] ins=new int[numCourses];//入度数
//        for (int i=0;i< prerequisites.length;i++){
//            int in=prerequisites[i][0],out=prerequisites[i][1];
//            arr[out][in]=1;
//            ins[in]++;
//        }
//        List<Integer> list=new ArrayList<>();
//        for (int i=0;i< numCourses;i++){
//            for (int j=0;j< ins.length;j++){
//                if (ins[j]==0&&!list.contains(j)){//入度为0
//                    list.add(j);
//                    int[] curOut=arr[j];
//                    for (int k=0;k<curOut.length;k++){
//                        if (curOut[k]==1) ins[k]--;
//                    }
//                    break;
//                }
//            }
//        }
//        if (list.size()!=numCourses) return new int[0];
//        int[] result=new int[list.size()];
//        for (int i=0;i<list.size();i++){
//            result[i]=list.get(i);
//        }
//        return result;
    }
}

class Offer114{
    static final int VISITING = 1, VISITED = 2;
    Map<Character, List<Character>> edges = new HashMap<Character, List<Character>>();
    Map<Character, Integer> states = new HashMap<Character, Integer>();
    boolean valid = true;
    char[] order;
    int index;

    public String alienOrder(String[] words) {
        int length = words.length;
        for (String word : words) {
            int wordLength = word.length();
            for (int j = 0; j < wordLength; j++) {
                char c = word.charAt(j);
                edges.putIfAbsent(c, new ArrayList<Character>());
            }
        }
        for (int i = 1; i < length && valid; i++) process2(words[i - 1], words[i]);
        order = new char[edges.size()];
        index = edges.size() - 1;
        Set<Character> letterSet = edges.keySet();
        for (char u : letterSet) {
            if (!states.containsKey(u)) process1(u);
        }
        if (!valid) return "";
        return new String(order);
    }

    public void process2(String before, String after) {
        int length1 = before.length(), length2 = after.length();
        int length = Math.min(length1, length2);
        int index = 0;
        while (index < length) {
            char c1 = before.charAt(index), c2 = after.charAt(index);
            if (c1 != c2) {
                edges.get(c1).add(c2);
                break;
            }
            index++;
        }
        if (index == length && length1 > length2) valid = false;
    }

    public void process1(char u) {
        states.put(u, VISITING);
        List<Character> adjacent = edges.get(u);
        for (char v : adjacent) {
            if (!states.containsKey(v)) {
                process1(v);
                if (!valid) return;
            } else if (states.get(v) == VISITING) {
                valid = false;
                return;
            }
        }
        states.put(u, VISITED);
        order[index] = u;
        index--;
    }
}

class Offer115{
    public boolean sequenceReconstruction(int[] nums, int[][] sequences) {//拓扑排序
        int n = nums.length;
        int[] ins = new int[n + 1];
        Set<Integer>[] graph = new Set[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new HashSet<Integer>();
        }
        for (int[] sequence : sequences) {
            int size = sequence.length;
            for (int i = 1; i < size; i++) {
                int prev = sequence[i - 1], next = sequence[i];
                if (graph[prev].add(next)) {
                    ins[next]++;
                }
            }
        }
        Queue<Integer> queue = new ArrayDeque<Integer>();
        for (int i = 1; i <= n; i++) {
            if (ins[i] == 0) queue.offer(i);
        }
        while (!queue.isEmpty()) {
            if (queue.size() > 1) return false;//队列中元素始终仅含一个保证了唯一性
            int num = queue.poll();
            Set<Integer> set = graph[num];
            for (int next : set) {
                ins[next]--;
                if (ins[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        return true;
    }
}

class Offer116{
    class unionFind{
        int branch;
        int[] parents;
        public unionFind(int n){
            this.branch=n;
            parents=new int[n];
            for (int i=0;i<n;i++) parents[i]=i;
        }
        public int find(int n){//顶层元素
            while (parents[n]!=n){
                n=parents[n];
            }
            return n;
        }
        public void union(int n1,int n2){//合并
            parents[find(n1)]=find(n2);
            this.branch--;
        }
    }
    public int findCircleNum(int[][] isConnected) {
        int length= isConnected.length;
        unionFind unionFind=new unionFind(length);
        for (int i=0;i<length;i++){
            for (int j=0;j<length;j++){
                if (isConnected[i][j]==1&&unionFind.find(i)!= unionFind.find(j)){
                    unionFind.union(i,j);
                }
            }
        }
        return unionFind.branch;
    }
}

class Offer117{
    int[] parents;
    public boolean process(char[] str1,char[] str2){//判断相似
        List<Integer> list=new ArrayList<>();
        for (int i=0;i< str2.length;i++){
            if (str1[i]!=str2[i]) {
                list.add(i);
            }
        }
        if (list.size()==0) return true;
        if (list.size()==2&&str1[list.get(0)]==str2[list.get(1)]&&str1[list.get(1)]==str2[list.get(0)]) return true;
        return false;
    }

    public int find(int i){
        while (parents[i]!=i){
            i=parents[i];
        }
        return i;
    }

    public void  union(int i,int j){
        parents[find(i)]=find(j);
    }

    public int numSimilarGroups(String[] strs) {
        char[][] words=new char[strs.length][];
        parents=new int[strs.length];
        int brunch= words.length;
        for (int i=0;i< words.length;i++) parents[i]=i;
        for (int i=0;i< strs.length;i++){
            words[i]=strs[i].toCharArray();
        }
        for (int i=0;i< words.length;i++){
            for (int j=i+1;j< words.length;j++){
                if (process(words[i],words[j])&&find(i)!=find(j)){//相似且为合并
                    union(i,j);
                    brunch--;
                }
            }
        }
        return brunch;
    }
}

class Offer118{
    int[] parents;
    public int process1(int node){//寻找顶层元素
        while (parents[node]!=node){
            node=parents[node];
        }
        return node;
    }
    public void process2(int node1,int node2){//合并量集合
        parents[process1(node1)]=process1(node2);
    }
    public int[] findRedundantConnection(int[][] edges) {
        int length= edges.length;
        parents=new int[length+1];
        for (int i=1;i<=length;i++) parents[i]=i;
        for (int i=0;i<length;i++){
            int node1=edges[i][0],node2=edges[i][1];
            if (process1(node1)!=process1(node2)){
                process2(node1,node2);
            }else return edges[i];
        }
        return null;
    }
}

class Offer119{
    public int longestConsecutive(int[] nums) {
        if (nums.length==0) return 0;
        Arrays.sort(nums);
        int left=0,right=0,max=0,count=1;
        while (true){
            if (right== nums.length-1) break;//末位元素
            if (nums[right+1]-nums[right]==1){//满足连续
                right++;
                count++;
            }else if (nums[right+1]==nums[right]){
                right++;
            }else {//不满足连续
                max=Math.max(max,count);
                count=1;
                right++;
                left=right;
            }
        }
        max=Math.max(max,count);
        return max;
    }
}